/*
 * Sorter.java
 * Copyright: XYZ Org (c) 2015
 */
package org.liang.agile.sort;

/**
 * 排序器.
 * 
 * <pre>
 * 简单实现 一下排序：
 * (1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
 * (2)、选择排序：简单选择排序、堆排序。
 * (3)、交换排序：冒泡排序、快速排序。
 * (4)、归并排序
 * (5)、基数排序
 * </pre>
 * 
 * @author L.Yang
 * @version v1.0 2016年5月17日 下午7:44:10
 */
public class Sorter {


    /**
     * 冒泡排序.
     * 
     * <pre>
     * 原理: 临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
     * 
     * 这样一趟过去后,最大或最小的数字被交换到了最后一位,
     * 
     * 然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子。
     * </pre>
     * 
     * @param datas
     *            待排序数组
     * @return 排序后数组
     */
    public double[] bubblesort(double[] datas) {
        for (int i = 0, len = datas.length; i < len - 1; i++) {
            for (int j = len - 1; j > i; j--) {
                if (datas[j - 1] > datas[j]) {
                    swap(datas, j, j - 1);
                }
            }
        }
        return datas;
    }

    private void swap(double[] datas, int i, int j) {
        if (i != j) {
            double temp = datas[i];
            datas[i] = datas[j];
            datas[j] = temp;
        }
    }

    /**
     * 快速排序.
     * 
     * <pre>
     * 原理: 将最左边的数设定为基准值，并记录其值为base
     *  循环处理： 
     *     令索引j 从数列左右方往左方找，直到找到大于base 的数 
     *     令索引i 从数列左方往右方找，直到找到小于base 的数 
     *     如果i >= j，则离开循环 
     *     如果i < j，则交换索引i与j两处的值 
     *     将左侧的轴与j 进行交换 
     *     对轴左边进行递回 
     *     对轴右边进行递回
     * </pre>
     * 
     * @param datas
     *            待排序数组
     * @return 排序后数组
     */
    public double[] quicksort(double[] datas) {
        return quicksort(datas, 0, datas.length - 1);
    }

    double[] quicksort(double datas[], int left, int right) {
        if (left < right) {
            double base = datas[left];
            int i = left, j = right;
            while (i < j) {
                // 从右向左找第一个小于base的数
                while (i < j && datas[j] >= base)
                    j--;
                if (i < j)
                    datas[i++] = datas[j];
                // 从左向右找第一个大于等于base的数
                while (i < j && datas[i] < base)
                    i++;
                if (i < j)
                    datas[j--] = datas[i];
            }
            datas[i] = base;
            // 递归调用
            quicksort(datas, left, i - 1);
            quicksort(datas, i + 1, right);
        }
        return datas;
    }
}
